/*
 * Copyright 1999-2011 Alibaba Group.
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package com.alibaba.dubbo.rpc.cluster.loadbalance;

import com.alibaba.dubbo.common.Constants;
import com.alibaba.dubbo.common.URL;
import com.alibaba.dubbo.rpc.Invocation;
import com.alibaba.dubbo.rpc.Invoker;
import com.alibaba.dubbo.rpc.RpcStatus;

import java.util.List;
import java.util.Random;

/**
 * LeastActiveLoadBalance 【基于加权最小活跃数算法实现的】
 * 最少活跃调用数，相同活跃数的随机，活跃数指调用前后计数差。
 * 使慢的提供者收到更少请求，因为越慢的提供者的调用前后计数差会越大。
 *
 * @author william.liangf
 */
public class LeastActiveLoadBalance extends AbstractLoadBalance {

    public static final String NAME = "leastactive";

    private final Random random = new Random();

    /**
     * 初始情况下，所有服务提供者活跃数均为0。活跃数代表着正在处理中的请求个数。
     * 每收到一个请求，活跃数加1，完成请求后则将活跃数减1。
     * 在服务运行一段时间后，性能好的服务提供者处理请求的速度更快，因此活跃数下降的也越快，此时这样的服务提供者能够优先获取到新的服务请求，
     * 这就是最小活跃数负载均衡算法的基本思想。
     *
     * 除了最小活跃数，LeastActiveLoadBalance 在实现上还引入了【权重值】。准确的来说，LeastActiveLoadBalance 是基于加权最小活跃数算法实现的。
     *
     * @param invokers
     * @param url
     * @param invocation
     * @param <T>
     * @return
     */
    @Override
    protected <T> Invoker<T> doSelect(List<Invoker<T>> invokers, URL url, Invocation invocation) {
        // 总个数
        int length = invokers.size();
        // 当前最小活跃数
        int leastActive = -1;
        // 收集到的最小活跃数的个数, 最大也大不过 length, 在收集过后这个值可以知道数组中有效值的个数。
        int leastCount = 0;
        // 收集到的最小活跃数的下标集合, 多个时候依次填充。
        // 数组后边可能有无效数据, 也可能有剩余位置, 用 leastCount 知道到底有多少个值是有效的。
        int[] leastIndexs = new int[length];
        // 最小活跃候选者的总权重
        int totalWeight = 0;
        // 第一个权重，用于计算是否相同
        int firstWeight = 0;
        // 最小活跃的候选者中, 是否每个权重都相同
        boolean sameWeight = true;
        for (int i = 0; i < length; i++) {
            Invoker<T> invoker = invokers.get(i);
            // 活跃数
            int active = RpcStatus.getStatus(invoker.getUrl(), invocation.getMethodName()).getActive();
            // 权重 - 这个权重是没被 Warmup 做过降权处理的，新版本代码修改了这里，把拿到的weight做了降权处理。
            //        如果不算降权逻辑进去，拿到的权重为原始权重，那么totalWeight为总原始权重值。
            int weight = invoker.getUrl().getMethodParameter(invocation.getMethodName(), Constants.WEIGHT_KEY, Constants.DEFAULT_WEIGHT);

            if (leastActive == -1               // 第一次循环初始化
                    || active < leastActive) {  // 或者 发现更小的活跃数, 重新统计

                leastActive = active;           // 记录最小活跃数
                leastCount = 1;                 // 重新统计相同最小活跃数的个数
                leastIndexs[0] = i;             // 重新记录最小活跃数下标
                totalWeight = weight;           // 重新累计总权重
                firstWeight = weight;           // 当前发现的最小活跃数的权重（第一个候选者为第一个被发现的候选者,是一种『特殊情况』）
                sameWeight = true;              // 还原权重相同标识

            } else if (active == leastActive) { // 之前记录的最小的活跃数和当前活跃数相同

                leastIndexs[leastCount++] = i;  // 把当前候选者下标记录到数组中
                totalWeight += weight;          // 累计总权重

                // 如果当前权重相同标识为【相同】,用当前候选者权重 重新计算这个标识
                if (sameWeight                  // 【相同】
                        && i > 0                // always true
                        && weight != firstWeight// 当前权重值是否和第一个权重值相同
                ) {
                    // 也就是说，有一个不同时这个标识就为false, 并且不再做第二次判断
                    // 除非这个标识被新发现最小活跃数时重置
                    sameWeight = false;
                }
            }
            // else {}                          // 其他大于当前最小活跃数的忽略处理
        }

        // 到这里就已经把所有最小活跃数的候选者下标找到了
        // leastIndexs 记录最小活跃者下标、leastCount 记录数组中有效的元素个数
        // assert(leastCount > 0)
        if (leastCount == 1) {
            // 如果只有一个最小则直接返回
            return invokers.get(leastIndexs[0]);
        }

        if (!sameWeight && totalWeight > 0) {

            // 如果权重不相同且权重大于0则按总权重数随机, 算法同 RandomLoadBalance
            // 这里新版本修改过 变成 random.nextInt(totalWeight) + 1;
            // 比如有一组权重[7,2,1],那么随机出来的数最大为9, 而在for循环中用的 offsetWeight <= 0, 永远也选不到
            // RandomLoadBalance 就没有这个问题，因为用的是 offset < 0
            int offsetWeight = random.nextInt(totalWeight);

            // 并确定随机值落在哪个片断上
            for (int i = 0; i < leastCount; i++) {
                int leastIndex = leastIndexs[i];

                // 这里getWeight拿到的权重是经过 warmup 降权处理的，那么这个值可能比原始权重值小
                // 但是totalWeight的总值为原始权重值总和
                // 这就会导致经过计算过后offsetWeight可能永远也不会 <= 0, 导致无法选中 invoker
                // 所以新版代码修改了计算 totalWeight 的逻辑
                // 参看：http://dubbo.apache.org/zh-cn/docs/source_code_guide/loadbalance.html
                offsetWeight -= getWeight(invokers.get(leastIndex), invocation);

                if (offsetWeight <= 0) {
                    return invokers.get(leastIndex);
                }
            }
        }
        // 如果权重相同或权重为0则均等随机
        return invokers.get(leastIndexs[random.nextInt(leastCount)]);
    }
}